package cn.xiaolang.function.data_structure;

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * <h2>一致性hash算法实现</h2>
 * <p>
 * S类封装了机器节点的信息，如name、password、ip、port等
 * <p>
 * ^：相或问题
 * >>：位运算，右移位丢弃，如果该数为正,则高位补0,若为负数,则高位补1；ex:
 * 15>>2 ==> 3 ( 0000 1111 -> 右移0000 0011);
 * // 负数：取反码再补1
 * -15>>2 ==> -4 (负数源码1000 1111 ->  反码1111 0000 -> 补码 1111 0001(-15) -> 右移1111 1100  -> 减1 1111 1011 -> 取反 0000 0100 -> 源码 1000 0100 -> -4)
 * >>>: 位运算，逻辑右移，为正为负,则高位都补0；PS: 只是对32位和64位的值有意义。
 * 15>>>2 ==> 3 （0000 1111 -> 0000 0011）
 * <p>
 * (-15)   1111 1111 1111 1111 1111 1111 1111  0001
 * (>>2)   0011 1111 1111 1111 1111 1111 1111  1100
 * (-1)    0011 1111 1111 1111 1111 1111 1111  1011
 * (反码+1：正数反码不变)   0011 1111 1111 1111 1111 1111 1111  1100
 * (转10进制) 1073741820
 * <p>
 * -15>>>2 ==> -4 (负数源码1000 1111 ->  反码1111 0000 -> 补码 1111 0001(-15) -> 右移0011 1100  -> 减1 0011 1011 -> 取反 1100 0100 -> 源码 0100 0100 -> -4)
 * </p>
 *
 * @author Dean
 * @date 2021-10-19
 */
public class DistributedHash<S> {


    // 虚拟节点
    private TreeMap<Long, S> nodes;
    // 真实节点
    private final List<S> shards;
    // 每个真实节点对应的虚拟节点的个数
    private static final int NODE_NUM = 100;

    public DistributedHash(List<S> shards) {
        this.shards = shards;
        init();
    }

    /**
     * 初始化hash环
     */
    private void init() {
        this.nodes = new TreeMap<>();
        for (int i = 0; i != shards.size(); i++) {
            // 真实节点关联虚拟节点
            final S shardInfo = shards.get(i);
            for (int j = 0; j < NODE_NUM; j++) {
                nodes.put(hash("SHARD-" + i + "-NODE-" + j), shardInfo);
            }
        }
    }

    public S getShardInfo(String key) {
        // 沿环顺时针找到第一个虚拟节点
        SortedMap<Long, S> tail = nodes.tailMap(hash(key));
        if (tail.size() == 0) {
            return nodes.get(nodes.firstKey());
        }
        // 返回该虚拟节点对应的真实节点信息
        return tail.get(tail.firstKey());
    }

    /**
     * MurMurHash算法，是非加密HASH算法，性能很高，
     * 比传统的CRC32, MD5，SHA-1（这两个算法都是加密HASH算法，复杂度本身就很高，带来的性能上的损害也不可避免）
     * 等HASH算法要快很多，而且据说这个算法的碰撞率很低.
     * <a>http://murmurhash.googlepages.com/</a>
     */
    private Long hash(String key) {
        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());
        int seed = 0x1234ABCD;
        ByteOrder byteOrder = buf.order();
        buf.order(ByteOrder.LITTLE_ENDIAN);
        long m = 0xc6a4a7935bd1e995L;
        int r = 47;
        long h = seed ^ (buf.remaining() * m);
        long k;
        while (buf.remaining() >= 8) {
            k = buf.getLong();
            k *= m;
            k ^= k >>> r;
            k *= m;
            h ^= k;
            h *= m;
        }
        if (buf.remaining() > 0) {
            ByteBuffer finish = ByteBuffer.allocate(8).order(
                    ByteOrder.LITTLE_ENDIAN);
            //for big-endian version, do this first: <code> finish.position(8-buf.remaining());</code>
            finish.put(buf).rewind();
            h ^= finish.getLong();
            h *= m;
        }
        h ^= h >>> r;
        h *= m;
        h ^= h >>> r;
        buf.order(byteOrder);
        return h;
    }

}


